# -*- coding: utf-8 -*-

'''
insertion.py
Created on Junho de 2013
@authors: 
    Ricardo Barros, ESTIG,  EI pós-laboral n.º 5137
    Sergio Santos, ESTIG,  EI pós-laboral n.º 5626
'''

"""
O algoritmo "Insertion Sort"

Tempo de execução:
    Melhor caso O(n);
    Pior O(n^2).

Problema: ordenaç˜ao (crescente) de uma sequência de números inteiros.
O problema será resolvido com a sequência implementada como um vector ("array")
que será reordenado (não é criada uma nova sequência).

Tempo de execução depende dos dados de entrada:
    - dimens˜ao
    - "grau" prévio de ordenação

A sequência a ordenar está disposta entre as posições 1 e N de um vector.

Melhor Caso: sequência está ordenadada à partida
Pior Caso: sequência previamente ordenada por ordem inversa (decrescente)

Como utilizar:
 - EXEMPLO: Ordenação do array A:
 
    A=[5,2,4,6,1,3]
    insertionsort(A)
    print A

RESULTADO:
[1, 2, 3, 4, 5, 6]
>>>

"""

def insertionSort (A):
    for x in xrange(1,len(A)):
        key = A[x]
        i = x - 1
        while i > -1 and A[i] > key:
            A[i+1] = A[i]
            i = i - 1
        A[i+1] = key
